/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2023-12-25
 * Time:22:43
 */

/**
 * 980. 不同路径 III
 * 困难
 * 在二维网格 grid 上，有 4 种类型的方格：
 *     1 表示起始方格。且只有一个起始方格。
 *     2 表示结束方格，且只有一个结束方格。
 *     0 表示我们可以走过的空方格。
 *     -1 表示我们无法跨越的障碍。
 * 返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。
 * 每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。
 * 示例 1：
 * 输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
 * 输出：2
 * 解释：我们有以下两条路径：
 * 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
 * 2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
 */
public class uniquePathsIII {
    int m,n,step,ret;
    boolean[][] vis;
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    public int uniquePathsIII(int[][] grid) {
        m = grid.length;n = grid[0].length;
        vis = new boolean[m][n];
        int bx = 0,by = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) step++;
                else if (grid[i][j] == 1){
                    bx = i;by = j;
                }
            }
        }
        step += 2;
        vis[bx][by] = true;
        dfs(grid,bx,by,1);
        return ret;
    }

    private void dfs(int[][] grid, int i, int j, int count) {
        if (grid[i][j] == 2){
            if (count == step){
                ret++;
            }
            return;
        }
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k],y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] != -1){
                vis[x][y] = true;
                dfs(grid,x,y,count + 1);
                vis[x][y] = false;
            }
        }
    }
}
